package com.love.labuladong.dynamic;

/**
 * @Author : zh
 * @Description : 动态规划 ---> 斐波那契数
 * @Date : 2024-06-25 11:18
 */
public class FBNums {

    public static void main(String[] args) {
        int fid = fid(10);
        System.out.println(fid);
        int fid2 = fid2(10);
        System.out.println(fid2);
        int fid3 = fid3(10);
        System.out.println(fid3);
    }


    /**
     * 自顶向下 dp
     * @param n
     * @return
     */
    static int fid(int n){
        // index [0...n]
        int[] dp = new int[n+1];
        return process(dp,n);
    }



   static int process(int[] dp,int n){
        if(n == 1 || n == 2){
            return 1;
        }
        if(dp[n] != 0){
            return dp[n];
        }
        dp[n] = process(dp,n-1) + process(dp,n-2);
        return dp[n];
    }

    /**
     * 自底向上dp
     * @param n
     * @return
     */
    static int fid2(int n){
        // dp[i] ： fid(i) 对应得值
        // 由定义得出最终的结果就是取 dp[i],朝着这个方向去
        int[] dp = new int[n + 1];
        dp[0] = 0;  // dp[0] 其实是用不到的 只用到 dp[1...n]
        dp[1] = 1;  // dp[1] 和 dp[2] 由题可知
        dp[2] = 1;
        // dp[1] 和 dp[2]已知，现在计算 dp[3...n]
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i -1] + dp[i - 2];
        }
        return dp[n];
    }

    static int fid3(int n){
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int pre = 0;
        int fix = 1;
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            temp = pre + fix;
            pre = fix;
            fix = temp;
        }
        return fix;
    }

}
